package leetcode.code1690;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

// 记忆化中最快的
public class Solution2 implements IDebug {

	int[] stones;
	int[] sums;

	public int stoneGameVII(int[] stones) {
		this.stones = stones;
		int len = stones.length;
		sums = new int[len + 1];
		for (int i = 1; i < sums.length; i++) {
			sums[i] = sums[i - 1] + stones[i - 1];
		}
//		Map<String, int[]> dp1 = new HashMap<>();
//		Map<String, int[]> dp2 = new HashMap<>();
		Integer[][] dp1 = new Integer[len][len];
		Integer[][] dp2 = new Integer[len][len];
		int ans = this.alice(0, len - 1, dp1, dp2);
		return ans;
	}

	private int alice(int l, int r, Integer[][] dp1, Integer[][] dp2) {
		if (l + 1 == r) {
			return this.stones[l] <= this.stones[r] ? this.stones[r] : this.stones[l];
		}
		if (dp1[l][r] != null) {
			return dp1[l][r];
		}
		int ans1 = this.bob(l + 1, r, dp1, dp2);
		ans1 += this.sums[r + 1] - this.sums[l + 1];
		int ans2 = this.bob(l, r - 1, dp1, dp2);
		ans2 += this.sums[r] - this.sums[l];
		int ans = ans1 >= ans2 ? ans1 : ans2;
		dp1[l][r] = ans;
		return ans;
	}

	private int bob(int l, int r, Integer[][] dp1, Integer[][] dp2) {
		if (l + 1 == r) {
			return this.stones[l] <= this.stones[r] ? -this.stones[r] : -this.stones[l];
		}
		if (dp2[l][r] != null) {
			return dp2[l][r];
		}
		int ans1 = this.alice(l + 1, r, dp1, dp2);
		ans1 -= this.sums[r + 1] - this.sums[l + 1];
		int ans2 = this.alice(l, r - 1, dp1, dp2);
		ans2 -= this.sums[r] - this.sums[l];
		int ans = ans1 >= ans2 ? ans2 : ans1;
		dp2[l][r] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(6, this.stoneGameVII(H.str2array3("[5,3,1,4,2]")));
//		H.compare(122, this.stoneGameVII(H.str2array3("[7,90,5,1,100,10,10,2]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		char c = '\u0000';
//		System.out.println(c==d);
//		System.out.println('\u0020'==' ');
//		System.out.println(d==' ');
//		System.out.println(c==' ');
//		System.out.println(c==(char)32);
//		System.out.println((char)32);
	}

}
